#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct BiTNode{
	char data;
	struct BiTNode* lchild;
	struct BiTNode* rchild;
}BiTNode,*BiTree;
typedef struct LinkNode{  //用以二叉树的层序遍历的队列
	char data;
	struct LinkNode *next;
}LinkNode;
typedef struct {		//用以二叉树的层序遍历的队列  存储头结点和尾节点
	struct LinkNode *head;
	struct LinkNode *rear;
}LinkQueque;
void LinkQuqueInit(LinkQueque **Q){
	(*Q) = (LinkQueque*)malloc(sizeof(LinkQueque));
	(*Q)->head = (*Q)->rear = (LinkNode*) malloc(sizeof(LinkQueque));
	(*Q)->head->next = NULL;
}
bool IsEmpty(LinkQueque *Q){
	if(!Q->head->next){
		return true;
	}
	return false;
}
void Enqueue(LinkQueque *Q,char data){
	LinkNode *newNode = (LinkNode*)malloc(sizeof(LinkNode));
	newNode->data= data;
	Q->rear->next = newNode;
	newNode->next = NULL;
	Q->rear = newNode;
}
char OutQueue(LinkQueque *Q){
	if(IsEmpty(Q)){
		printf("队列已空\n");
	}
	char data;
	LinkNode *p  = Q->head->next;
	data = p->data;
	Q->head->next = p->next;
	if(Q->rear == p){
		Q->rear = Q->head;
	}
	free(p);
	return data;
}
void CreateTreeByPre(BiTree *T){  //通过先序遍历生成二叉树
	char data;
	scanf("%c",&data);
	if(data=='#'){
		*T = NULL;  //假如输入#为空，那么该节点为空
	}
	else {
		*T = (BiTNode*)malloc(sizeof(BiTNode));
		(*T)->data = data;
		CreateTreeByPre(&(*T)->lchild);
		CreateTreeByPre(&(*T)->rchild);
	}
}
void PreOrder(BiTree T){
	if(T){
		printf("%c",T->data);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
	return;
}
void MidOrder(BiTree T){
	if(T){
		MidOrder(T->lchild);
		printf("%c",T->data);
		MidOrder(T->rchild);
	}
	return;
}
void LastOrder(BiTree T){
	if(T){
		LastOrder(T->lchild);
		LastOrder(T->rchild);
		printf("%c",T->data);
	}
	return;
}
void FloorOrder(BiTree T){//二叉树的层序遍历
	LinkQueque *Q = NULL;
	LinkQuqueInit(&Q);
	Enqueue(Q, T->data);
	while (!IsEmpty(Q)) {
		printf("%c",OutQueue(Q));
		if(T->lchild){
			Enqueue(Q, T->lchild->data);
		}
		if(T->rchild){
			Enqueue(Q, T->rchild->data);
		}
	}
}
int main(int argc, char *argv[]) {
	BiTree T = NULL;
	printf("现在请你输入字符串来构建数,#表示节点空:");
	CreateTreeByPre(&T);
	PreOrder(T);
	printf("\n");
	MidOrder(T);
	printf("\n");
	LastOrder(T);
	printf("\n");
//	FloorOrder(T);
}